package mao.algorithm.sort;

/**
 * @author Totoro
 * @date 2020/7/10
 * @explain: 快速排序的第二种写法。
 */
public class FastSort2 {
    private  void fastSort(int [] data){
        fastSort(data,0,data.length-1 ) ;
    }
    private  void fastSort(int [] data,int start,int end) {
        int partition = partition(data, start, end);
        //这里需要进行判断，总需要个递归结束条件
        if (start < partition-1){
            fastSort(data,start,partition-1);
        }
       if (partition-1 < end){
           fastSort(data,partition+1,end);
       }
    }
    private  int partition(int[] num,int start,int end){
        if (start >= end) return start;
        int lo = start,hi = end+1,v=num[start];
        while (lo < hi){
            //注意这里不能是<=因为，
            while (++lo <= end && num[lo]<v);
            while (--hi >= start && num[hi]>v);
            if (lo>=hi) break;
            swap(num,lo,hi);
        }
        //hi 指向小于等于V的点，那么最后需要将num[hi]和num[start]交换，由于num[start]已经保存了，
        // 所以可以。简写处理。
        num[start] = num[hi];
        num[hi] = v;
        return hi;
    }
    private  void swap(int[] num,int from,int to){
        int tmp = num[from];
        num[from] = num[to];
        num[to] = tmp;
    }

    public  static void main(String[] args) {
        int [] data = {4,3,2,1};
        FastSort2 sort2 = new FastSort2();
        sort2.fastSort(data);
        for(int i =0;i<data.length;i++){
            System.out.println(data[i]);
        }
    }
}
